/*
 * @lc app=leetcode.cn id=1005 lang=typescript
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start
function largestSumAfterKNegations(nums: number[], k: number): number {
    const sorted = nums.sort((a, b) => a - b);
    let i = 0;
    while (k) {
        if (sorted[i] === 0) break;
        if (sorted[i] > 0) {
            // 随便重复就可以了
            if (k % 2 === 0) {
                break;
            } else {
                // 两个都是正数，所以比较哪一个比较小，这样删除最合适
                const now = sorted[i];
                const prev = sorted[i - 1];
                if (typeof prev === "number") {
                    if (now > prev) {
                        sorted[i - 1] = -sorted[i - 1];
                    } else {
                        sorted[i] = -sorted[i];
                    }
                } else {
                    // 没有前面，自己垫底
                    sorted[i] = -sorted[i];
                }
                break;
            }
        }
        sorted[i] = -sorted[i];
        i = i < sorted.length - 1 ? i + 1 : sorted.length - 1;
        k--;
    }
    return sorted.reduce((a, b) => a + b, 0);
}
// @lc code=end
